package arithmetic.LeetCode;

import org.junit.jupiter.api.Test;

/**
 * 74. 搜索二维矩阵
 * <p>
 * 编写一个高效的算法来判断m x n矩阵中，是否存在一个目标值。该矩阵具有如下特性：
 * 每行中的整数从左到右按升序排列。
 * 每行的第一个整数大于前一行的最后一个整数。
 * <p>
 * <p>
 * 示例 1：
 * 1,   3,  5,  7
 * 10,  11, 16, 20
 * 23,  30, 34, 60
 * <p>
 * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
 * 输出：true
 * <p>
 * 示例 2：
 * 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
 * 输出：false
 * <p>
 * <p>
 * 提示：
 * <p>
 * m == matrix.length
 * n == matrix[i].length
 * 1 <= m, n <= 100
 * -104 <= matrix[i][j], target <= 104
 * <p>
 * 链接：https://leetcode.cn/problems/search-a-2d-matrix
 *
 * @author jiangfeng on 2022/6/5
 */
public class Search2DMatrix {
    @Test
    public void test(){
        //int[][] a = new int[][]{{1,3,5,7},{10,11,16,20},{23,30,34,60}};
        int[][] a = new int[][]{{1,3}};
        System.out.println(searchMatrix(a,2));
    }
    public boolean searchMatrix(int[][] matrix, int target) {
        int left = 0, length = matrix.length, right = length - 1;
        if (matrix[left][0] > target || matrix[right][ matrix[right].length - 1] < target) {
            return false;
        }
        while (left <= right) {
            int mid = (left + right) / 2;
            // 检测边界
            if(searchMatrix(matrix[left], target)){
                return true;
            }
            if (searchMatrix(matrix[mid], target)) {
                return true;
            }
            if(searchMatrix(matrix[right], target)){
                return true;
            }
            if ((mid - 1)>=0 && matrix[mid - 1][matrix[0].length - 1] >= target) {
                right = mid - 1;
            } else if ( (mid + 1) <length && matrix[mid + 1][0] <= target) {
                left = mid + 1;
            } else {
                return false;
            }
        }
        return false;

    }

    public boolean searchMatrix(int[] a, int target) {
        int l = 0, r = a.length - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (a[l] == target || a[r] == target
                    || a[mid] == target) {
                return true;
            }
            if (a[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return false;
    }

    /**
     * 简洁版
     */
    @Test
    public void test2(){
        int[][] a = new int[][]{{1,3,5,7},{10,11,16,20},{23,30,34,60}};
        System.out.println(searchMatrix2(a,13));
    }

    public boolean searchMatrix2(int[][] matrix, int target) {
        int left = 0, length = matrix.length, right = length - 1;
        while (left <= right ) {
            if (matrix[left][0] > target || matrix[right][ matrix[right].length - 1] < target) {
                return false;
            }
            int mid = (left + right) / 2;
            // 检测边界
            if (searchMatri2x(matrix[mid], target)) {
                return true;
            }
            if (matrix[mid][0] > target) {
                right = mid - 1;
            } else if (matrix[mid][matrix[0].length-1] < target) {
                left = mid + 1 ;
            } else {
                return false;
            }
        }
        return false;

    }

    public boolean searchMatri2x(int[] a, int target) {
        int l = 0, r = a.length - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            // 左右不用重复判断
            if ( a[mid] == target) {
                return true;
            }
            if (a[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return false;
    }

    /**
     * 简洁版
     */
    @Test
    public void test3(){
        int[][] a = new int[][]{{1,3,5,7},{10,11,16,20},{23,30,34,60}};
        System.out.println(searchMatrix3(a,3));
    }

    /**
     * BST 二叉搜索树
     */
    public boolean searchMatrix3(int[][] matrix, int target) {
        int x =  matrix[0].length-1,y = 0,yMax = matrix.length-1;

        while(x>=0 && y<=yMax && matrix[y][x] !=target){
            if(matrix[y][x]>target){
                x--;
            }else{
                y++;
            }
        }
        if(x<0 || y> yMax || matrix[y][x] !=target){
            return false;
        }
        return true;

    }




}
